package homework2;

public class Problem5 {

	/**
	 * The driver for recursive median
	 * 
	 * @param args not used in this homework
	 */
	public static void main(String[] args) {
		int[] array1 = { 1, 10, 13, 21, 59 };
		int[] array2 = { 2, 16, 27, 39, 65 };
		if (array1.length == array2.length) {
			System.out.println("Median : " + getMedian(array1, array2, array1.length));
		} else {
			System.out.println("Arrays must be equal size");
		}
	}

	/**
	 * This method enters the recursive method and provides the arguments
	 * 
	 * @param array1 An array of sorted integers
	 * @param array2 Another array of sorted integers
	 * @param length The length of the array
	 * @return The median of the combined arrays
	 */
	private static int getMedian(int[] array1, int[] array2, int length) {
		return recursiveBinarySearch(array1, array2, 0, length - 1, length);
	}

	/**
	 * This method provides recursive implementation of a binary search.
	 * 
	 * @param array1 An array of sorted integers
	 * @param array2 Another array of sorted integers
	 * @param left Left array
	 * @param right Right array
	 * @param length The length of the array
	 * @return The median of the combined arrays
	 */
	private static int recursiveBinarySearch(int[] array1, int[] array2, int left,
			int right, int length) {
		int x, y;
		if (left > right) {
			return recursiveBinarySearch(array2, array1, 0, length - 1, length);
		}
		x = (left + right) / 2;
		y = length - x - 1;
		if (array1[x] > array2[y] && (y == length - 1 || array1[x] <= array2[y + 1]) ) {
			if (x == 0 || array2[y] > array1[x - 1]) {
				return (array1[x] + array2[y] )/ 2;
			} else {
				return (array1[x] + array1[x - 1]) / 2;
			}
		} else if (array1[x] > array2[y] && y != length - 1 &&  array1[x] > array2[y + 1]) {
			return recursiveBinarySearch(array1, array2, left, x - 1, length);
		} else {
			return recursiveBinarySearch(array1, array2, x + 1, right, length);
		}
	}

}
